package array

import (
	"gitee.com/ChanYeung/go-utils/debug"
	"math"
	"sort"
)

/**
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2jrse/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func twoSum(nums []int, target int) []int {
	m := make(map[int]int, 0)
	for i := 0; i < len(nums); i++ {
		expext := target - nums[i]
		if index, ok := m[expext]; ok {
			return []int{index, i}
		} else {
			m[nums[i]] = i
		}
	}
	return []int{}
}

/**
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]


作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2ba4i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func moveZeroes(nums []int) {
	//双指针，类似冒泡排序算法，将0交换到末尾去
	start := 0
	end := 0
	for end < len(nums) {
		if nums[start] == 0 {
			for end < len(nums) {
				//往后找到非0元素
				if nums[end] != 0 {
					break
				}
				end++
			}
			if !(end < len(nums)) {
				break
			}
			nums[start] = nums[end]
			nums[end] = 0

		}
		start++
		end++
	}
	debug.PrintArray[int](nums)
}

/**
旋转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。



示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func rotate(nums []int, k int) {
	//var tmp []int
	//tmp = append(tmp, nums[(len(nums)-k):]...)
	//tmp = append(tmp, nums[:len(nums)-k]...)
	//for i := range nums {
	//	nums[i] = tmp[i]
	//}

	//原地位移
	size := len(nums)
	index := 0
	hold := nums[0]
	visited := make([]bool, size)
	visited[0] = true
	for i := 0; i < size; i++ {
		xId := (index + k) % size
		if visited[xId] {
			//操作过
			nums[xId] = hold
			xId = (index + k + 1) % size
			visited[xId] = true
			hold = nums[xId]
			index = xId
		} else {
			tmp := nums[xId] //临时保留
			visited[xId] = true
			nums[xId] = hold
			hold = tmp
			index = xId
		}

	}
	debug.PrintArray(nums)
}
func swap(num []int, a, b int) {
	tmp := num[a]
	num[a] = num[b]
	num[b] = tmp

}

/**
加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func plusOne(digits []int) []int {
	size := len(digits)
	//不需要进位的场景
	if digits[size-1]+1 <= 9 {
		digits[size-1] += 1
		return digits
	}
	headIs9 := false
	for i := size - 1; i >= 0; i-- {
		if digits[i]+1 > 9 {
			if i == 0 {
				headIs9 = true
			}
			digits[i] = 0
		} else {
			digits[i] += 1
			break
		}
	}
	if headIs9 {
		//首位是9的话，会进一，补一位
		tmp := []int{1}
		tmp = append(tmp, digits...)
		return tmp
	}
	return digits
}

/**
两个数组的交集 II
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

解法1：使用map 存储第一个数组的数字出现次数，然后第二个数组遍历，key存在即值-1，并且add进list，记录出现次数
解法2：先排序，使用双指针 一次比较，然后移动小值的指针，直到比完

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func intersect(nums1 []int, nums2 []int) []int {
	//排序
	sort.Ints(nums1)
	sort.Ints(nums2)
	indexA := 0
	indexB := 0
	var result []int
	for indexA < len(nums1) && indexB < len(nums2) { //水桶短板效应，最短的那个数组遍历完即可
		if nums1[indexA] == nums2[indexB] {
			result = append(result, nums1[indexA])
			indexB++
			indexA++
		} else if nums1[indexA] < nums2[indexB] {
			//nums1 的数比较小，往后移动
			indexA++
		} else {
			indexB++
		}
	}
	return result
}

/**
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

解法：使用异或处理，异或满足交换律，所有元素异或后剩下的就是出现一次的数字


示例 1:

输入: [2,2,1]
输出: 1

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x21ib6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func singleNumber(nums []int) int {
	//异或运算，相异为真，相同为假，所以 a^a = 0 ;0^a = a
	//因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算，单独的值就剩下了
	tmp := 0
	for i := 0; i < len(nums); i++ {
		tmp ^= nums[i]
	}
	return tmp
}

//给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
func containsDuplicate(nums []int) bool {
	m := make(map[int]int, len(nums))
	for i := range nums {
		if _, ok := m[nums[i]]; ok {
			return true
		} else {
			m[nums[i]] += 1
		}
	}
	return false
}

//删除排序数组中的重复项
func removeDuplicates(nums []int) int {
	//0,0,1,1,1,2,2,3,3,4
	// 0, 1, 2, 3, 4
	replicateCount := 1
	left := 0
	for right := 0; right < len(nums); right++ {
		if nums[left] != nums[right] {
			left++
			nums[left] = nums[right] //两个位置值不一样，去重复
			replicateCount++
		}
	}
	return replicateCount

}

/**
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

//使用 动态规划的方式
func maxProfitWithDynamic(prices []int) int {
	if prices == nil || len(prices) < 2 {
		//说明 不能进行买卖，无法获得收益
		return 0
	}
	profitWithStock := float64(-1 * prices[0]) //i+1天 手里有股票的最大利润
	profitWithoutStock := float64(0)           //i+1天 手里没有股票的最大利润
	for i := 0; i < len(prices); i++ {
		//当天手里有股票
		profitWithStock = math.Max(profitWithStock, profitWithoutStock-float64(prices[i]))
		//当天手里没有股票
		profitWithoutStock = math.Max(profitWithStock+float64(prices[i]), profitWithoutStock)
	}
	return int(profitWithoutStock) //手里没有股票应该收益最大的
}
func maxProfitWithGreedy(prices []int) int {
	if prices == nil || len(prices) < 2 {
		//说明 不能进行买卖，无法获得收益
		return 0
	}
	index := 0
	days := len(prices)
	result := 0
	for index < days {
		//找到下降波峰的底部，可能没有，一开始就是上升波峰
		for index < days-1 && prices[index+1] <= prices[index] {
			index++
		}
		bottomPrice := prices[index]
		//找到上升波峰的顶
		for index < days-1 && prices[index+1] >= prices[index] {
			index++
		}
		//各个波段数据的综合
		result += prices[index] - bottomPrice
		index++
	}
	return result
}

/**
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func rotateImageMatrixUseChange(matrix [][]int) {
	//对称层 交换
	top := 0
	down := len(matrix) - 1
	for top <= down {
		tmp := matrix[top]
		matrix[top] = matrix[down]
		matrix[down] = tmp
		top++
		down--
	}
	//对角线交换元素
	/**
	1 2 3
	4 5 6
	7 8 9
	====
	[[7,4,1],
	[8,5,2],
	[9,6,3]]
	*/
	for i := 0; i < len(matrix[0]); i++ {
		for k := i + 1; k < len(matrix[i]); k++ {
			tmp := matrix[i][k]
			matrix[i][k] = matrix[k][i]
			matrix[k][i] = tmp
		}
	}
}

/**
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnumcr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func merge(nums1 []int, m int, nums2 []int, n int) {
	aTail := len(nums1) - 1
	front := m - 1 //nums1的最后一个元素
	n -= 1
	for n >= 0 {
		//nums2的最后一个元素和num1的最后一个元素比 大的元素沉底
		//因为已经有序了，所以直接放到最后即可,较少移动次数
		if front < 0 || nums1[front] <= nums2[n] { //nums1的都已经移动完了，nums2还没有完，nums2直接往前tie
			//nums2的数据大，放到最后  tail 指针-1(这个元素是最大的了，不用再比)
			nums1[aTail] = nums2[n]
			n-- //nums2 往前移，比较下一个 front 不动
		} else {
			//nums1的数比较大  沉底， front 迁移1位，继续和nums2刚刚的数据比较
			nums1[aTail] = nums1[front] //
			front--
		}
		aTail--
	}
	debug.PrintArray(nums1)

}

func isBadVersion(version int) bool { return true }

func firstBadVersion(n int) int {
	//if !isBadVersion(n-1) && isBadVersion(n) {
	//	return n
	//}
	//return firstBadVersion(n - 1)
	start := 1
	end := n
	//类似二分查找的思想:
	//n-1 是badversion n不是badversion （n则是第一个错误版本）
	for start < end {
		mid := (end-start)/2 + start
		if isBadVersion(mid) {
			//mid 之后的数据都是badversion true  所以往前找
			end = mid
		} else {
			//mid 不是 badversion，但不确定他的下一个是不是badversion，
			start = mid + 1
		}
	}
	return start

}

/**
最大子序和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn3cg3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

func maxSubArray(nums []int) int {
	//如果要计算前i+1个元素构成的连续子数组的最大和，也就是计算dp[i]，
	//只需要判断dp[i-1]是大于0还是小于0。如果dp[i-1]大于0，就继续累加，
	//dp[i]=dp[i-1]+num[i]。如果dp[i-1]小于0，
	//我们直接把前面的舍弃，也就是说重新开始计算，否则会越加越小的，直接让dp[i]=num[i]
	sum := make([]float64, len(nums))
	sum[0] = float64(nums[0])
	mx := sum[0]
	for i := 1; i < len(nums); i++ {
		sum[i] = math.Max(sum[i-1], float64(0)) + float64(nums[i])
		//这个sum有可能加上num[i]之后变小了，所以并不能去sum[length] 作为最终的结果
		mx = math.Max(sum[i], mx)
	}
	return int(sum[len(nums)-1])
}

/**
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？



示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn854d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func climbStairs(n int) int {
	if n <= 1 {
		return 1
	}
	return climbStairs(n-1) + climbStairs(n-2)

}
func climbStairsWithDynamic(n int) int {
	if n <= 1 {
		return 1
	}
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

func robWithDynamic(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	steal := float64(nums[0])
	noSteal := float64(0)
	for i := 1; i < len(nums); i++ {
		tmp := noSteal + float64(nums[i])
		noSteal = math.Max(steal, noSteal)
		steal = tmp

	}
	return int(math.Max(noSteal, steal))
}
func robWithDynamic2(nums []int) int {
	if len(nums) < 1 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	if len(nums) == 2 {
		return int(math.Max(float64(nums[0]), float64(nums[1])))
	}
	dp := make([]float64, len(nums))
	dp[0] = float64(nums[0])
	dp[1] = math.Max(float64(nums[0]), float64(nums[1]))
	max := math.Max(dp[0], dp[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = math.Max(dp[i-1], dp[i-2]+float64(nums[i])) //当前一家不偷 和偷当前这家最大利益 取max
		if dp[i] > max {
			max = dp[i]
		}
	}
	return int(max)

}

/**
利用加法思想  来交换元素
 a=1 b=2
a=a+b=3
b=a-b=3-2=1
a=a-b=3-1=2
*/
func swapNew(nums []int, a, b int) {
	if a != b {
		nums[a] = nums[a] + nums[b]
		nums[b] = nums[a] - nums[b]
		nums[a] = nums[a] - nums[b]
	}
}

/**
46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
*/
func permute(nums []int) [][]int {
	permuteInternal(nums, 0)
	return internalPermuteList
}

var internalPermuteList [][]int

func permuteInternal(nums []int, index int) {
	if index >= len(nums)-1 {
		debug.PrintArray(nums)
		//下标越界了，所以元素的交换情况已经结束，递归结束
		//tmp := make([]int, len(nums))
		//copy(tmp, nums)
		//internalPermuteList = append(internalPermuteList, tmp)
		return
	}
	for i := index; i < len(nums); i++ {
		swapNew(nums, i, index)
		permuteInternal(nums, index+1)
		swapNew(nums, index, i) //回溯，子结果不影响 父结果
	}
}

/**
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。
*/
func threeSum(nums []int) [][]int {
	//先排序，然后使用双指针，先选择一个数 然后对剩下的结果使用 使用双指针(头尾查找)计算两数之和
	sort.Ints(nums)
	var result [][]int
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			//第一个数大于 0，后面都是递增正数，不可能相加为零了
			return result
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
			//因为要保证是不重复的三元组合，所以直接跳过
		}
		pointer := twoSumWithPointer(nums, i, len(nums)-1)
		result = append(result, pointer...)
	}
	return result
}
func twoSumWithPointer(nums []int, staticPosition, end int) [][]int {
	var result [][]int
	start := staticPosition + 1
	for start < end {
		tmpSum := nums[start] + nums[end] + nums[staticPosition]
		//找到和为target 的两个数
		if tmpSum == 0 {
			result = append(result, []int{nums[staticPosition], nums[start], nums[end]})
			//继续找
			// 去重：第二个数和第三个数也不重复选取
			// 例如：[-4,1,1,1,2,3,3,3], i=0, left=1, right=5
			for start < end && nums[start] == nums[start+1] {
				start++
			}
			for start < end && nums[end] == nums[end-1] {
				end--
			}
			start++
			end--
		} else if tmpSum > 0 {
			end--
		} else {
			start++
		}
	}
	return result
}

/**
最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
*/
func threeSumClosest(nums []int, target int) int {
	if len(nums) <= 3 {
		sum := 0
		for _, x := range nums {
			sum += x
		}
		return sum
	}
	//先排序
	sort.Ints(nums)
	//找3数之和
	//记录最接近target的和差值  越小越接近target
	minSum := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
			//因为要保证是不重复的三元组合，所以直接跳过
		}
		start := i + 1
		end := len(nums) - 1
		for start < end {
			tmpSum := nums[start] + nums[end] + nums[i]
			//找到和为target 的两个数
			if tmpSum == target {
				//三元组与target和一致，没有更接近的了，直接返回
				minSum = tmpSum
				break
			}
			//更新最小和
			if math.Abs(float64(tmpSum-target)) < math.Abs(float64(minSum-target)) { //使用绝对距离
				minSum = tmpSum
			}
			if tmpSum > target {
				end--
			} else {
				start++
			}
		}
	}
	return minSum

}

//原地旋转90度 多维数组
//1 2 3 5
//4 5 6 7
//7 8 9 0
//6 4 5 1
func rotateMultiDimensionArray(matrix [][]int) {
	dimen := len(matrix)
	level := int(math.Ceil(float64(dimen)) / 2)
	for i := 0; i < level; i++ {
		for d := i; d < len(matrix[i])-i-1; d++ { //d 表示当前层 可遍历位置
			lt := matrix[i][d]                 //左上角
			rt := matrix[d][dimen-i-1]         //右上角
			lb := matrix[dimen-d-1][i]         //左下角
			rb := matrix[dimen-i-1][dimen-d-1] //右下角

			matrix[i][d] = lb                 //左上角<- 左下角
			matrix[dimen-d-1][i] = rb         //左下角<- 右下角
			matrix[dimen-i-1][dimen-d-1] = rt //右下角<- 右上角
			matrix[d][dimen-i-1] = lt         //右上角<- 左上角
		}
	}
}
